Problem statement: zenit13ski

Ak chce byť Maroško úspešný kandidát, musí demonštrovať schopnosť riešit obyčajné problémy obyčajných ľudí. Preto sa rozhodol, že navštívi dedinu Baranovce, odkiaľ mu nedávno poslala sťažnosť jeho potenciálna volička Lucia. Predmetom Luciinej sťažnosti je štekanie psov v noci.

Baranovce pozostávajú z jednej dlhej ulice, ktorá sa tiahne zo západu na východ. Na jednej strane tejto ulice sú v rade domy. Pozíciu domu budeme udávať jeho vzdialenosťou od západného začiatku dediny v metroch. Lucia býva na východnom konci dediny.

V záhradách niektorých domov pobehujú psy. Každý pes pri štekaní robí zvuk nejakej intenzity. Hlučnosť tohto zvuku je priamo úmerná vzdialenosti, kde tento zvuk počuť. Preto budeme pre každého psa uvažovať jeho doštek, ktorý budeme udávať v metroch.

Najzápadnejší pes je mierne neurotický a veľmi často sa rozšteká bez zjavnej príčiny. Všetky ostatné psy sa rozštekajú vtedy a len vtedy, ak počujú štekot iného psa. Štekanie sa šíri po sekundách. Pes, ktorý nešteká a začuje štekot iného psa začne štekať nasledujúcu sekundu. Ak nejaký pes šteká, bude štekať dlho (pre účely našej úlohy môžeme povedať donekonečna). Ak je nejaký pes presne na hranici došteku iného, počuje ho štekať.

Maroško chce overiť, či je Luciina sťažnosť relevantná. K dispozícii má mapu dediny, miesta, kde žijú psy a ich došteky. Zistite, či sa v prípade, že začne štekať najzápadnejší pes časom rozštekajú všetky psy v dedine a ak áno, o koľko sekúnd sa to stane.

Na prvom riadku vstupu prečítajte číslo N (2 ≤ N ≤ 1,000,000) - počet psov v dedine. Na zvyšných N riadkoch sa nachádzajú popisy psov. Popis psa číslo i pozostáva z čísel p_i a d_i - súradnice domu, kde žije a jeho doštek. Obe tieto čísla sú celé a medzi 1 a 1,000,000. Žiadne dva psy nežijú na rovnakom mieste. Môžete predpokladať, že psy sú utriedené podľa pozície, kde žijú.

V prípade, že nebude štekať celá dedina vypíšte na výstup nerozsteka sa cela dedina. V opačnom prípade vypíšte, o koľko sekúnd sa rozštekajú všetky psy. Poznámka: Keďže v tejto úlohe je veľký vstup, je potrebné ho načítavať rýchlo. Preto odporúčame podľa možností vyhnúť sa Pythonu, C# a streamom v C++. Pamäťový limit na tjeto úlohe je 256 MB.

4
1 3
4 7
6 2
10 4
 

2
 

5
2 4
3 3
4 2
5 1
7 7
 

nerozsteka sa cela dedina
 

6
1 11
5 24
10 17
25 14
33 7
39 11
 

3